package com.honeywen.mymvc.leetcode;

/**
 * 28. 实现strStr() https://leetcode-cn.com/problems/implement-strstr/description/
 *
 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

 示例 1:

 输入: haystack = "hello", needle = "ll"
 输出: 2
 * @author weiw@opera.com
 * @date 2018/8/29 下午9:32
 */
public class StrTest {


    public int strStr(String haystack, String needle) {

        if (haystack == null || needle == null) {
            return  -1;
        }

        if (needle.length() == 0) {
            return 0;
        }


        int len1 = haystack.length();
        int len2 = needle.length();

        for (int i = 0; i < len1; i++) {

            if (haystack.charAt(i) == needle.charAt(0)) {

                // 如果needle 就1位
                if (len2 == 1) {
                    return i;
                }

                // 如果haystack剩余没有needle长，返回 -1
                if (len1 - i < len2) {
                    return -1;
                }

                int j = 1;
                for (int k = 1; k < needle.length(); k++) {

                    if (needle.charAt(k) != haystack.charAt(i + k)) {
                        break;
                    }

                    j++;

                }

                if (j == len2) {
                    return i;
                }

            }

        }



        return -1;
    }

    public int strStr2(String haystack, String needle) {

        if (haystack == null || needle == null) {
            return -1;
        }

        int i, j = 0;

        for (i = 0; i < haystack.length() - needle.length() + 1; i++) {
            for (j = 0; j < needle.length(); j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }

            if (j == needle.length()) {
                return i;
            }

        }

        return -1;



    }

    public int strStr3(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    public int strStr4(String haystack, String needle) {

        if (haystack == null || needle == null) {
            return -1;
        }

        if (needle.length() == 0) {
            return 0;
        }

        int max = haystack.length() - needle.length();

        char first = needle.charAt(0);
        for (int i = 0; i <= max; i++) {

            if (haystack.charAt(i) != first) {
                while(++i <= max && haystack.charAt(i) != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + needle.length() - 1;
                for (int k = 1; j < end && haystack.charAt(j)
                        == needle.charAt(k); j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i;
                }
            }

        }



        return -1;
    }


    public static void main(String[] args) {

        StrTest strTest = new StrTest();
        int x = strTest.strStr("aaa", "aaa");
        System.out.println(x);
        System.out.println(strTest.strStr4("aaa", "aaa"));


    }
}
